HDU_5800

描述

令dp[i][j][s1][s2]表示前i个物品填了j的体积，有s1个物品选为为必选，s2个物品选为必不选的方案数(0<=s1,s2<=2)，则有转移方程dp[i][j][s1][s2] = dp[i - 1][j][s1][s2] + dp[i - 1][j - a[i]][s1 - 1][s2] + dp[i - 1][j][s1][s2 - 1] + dp[i - 1][j - a[i]][s1][s2]，边界条件为dp[0][0][0][0] = 1，时间复杂度O(NS*3^2)。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <complex>
#include <cstdio>
using namespace std;
#define ll long long
#define mod 1000000007
#define maxn 1008
int dp[maxn][maxn][3][3];
int a[maxn];
inline void add(int &a,int b)
{
    a = (a + b)%mod;
}
int main(){
    int T;
    for(cin>>T;T;T--){
        memset(dp,0,sizeof(dp));dp[0][0][0][0]=1;
        int n,s;scanf("%d%d",&n,&s);
        for(int i=1 ; i<=n ; i++)
            scanf("%d",&a[i]);
        for(int i=1;i<=n;i++){
            for(int j=0; j<=s ; j++){
                for(int k=0 ; k<3 ;k++){
                    for(int l=0 ; l<3 ;l++){
                        add(dp[i][j][k][l],dp[i-1][j][k][l]);
                        if(j>=a[i])add(dp[i][j][k][l],dp[i-1][j-a[i]][k][l]);
                        if(j>=a[i] && k>0)add(dp[i][j][k][l],dp[i-1][j-a[i]][k-1][l]);
                        if(l>0)add(dp[i][j][k][l],dp[i-1][j][k][l-1]);
                    }
                }
            }
        }
        ll ans=0;
        for(int i=0;i<=s;i++)
            ans = (ans+dp[n][i][2][2])%mod;
        //因为必取的两个和必不取的两个在公式中是又先后顺序的，当时dp中没有顺序，所以要乘以4
        printf("%I64d\n", ans*4%mod);
    }
    return 0;
}